1. Technical Field
The technology described in this patent application is generally directed to computer-implemented systems and processes for solving complex optimization problems, and more particularly to optimization problems involving non-linear objective functions.
2. Description of the Related Art
Complex problems are often characterized by a series of functions, each function typically including one or more parameters. In the field of computerized optimization, such problems may be solved by generating a mathematical model of the problem that is referred to as a program. Optimization programs are typically either linear or non-liner programs. Linear programs consist of an objective function and a series of constraint functions, each of which is a linear equation. Such programs are fairly easy to solve. Non-linear programs, however, typically involve complex objective functions comprising several non-linear equations that can be much more difficult to solve and/or optimize. For a more complete discussion of linear and non-linear programs, see “Linear and Nonlinear Programming, Second Edition,” by David G. Luenberger, 2005, the entirety of which is incorporated herein by reference.
Non-linear programs or models having a limited-domain objective function can be difficult to solve because the objective function and/or its derivatives may fail at some point in the parameter space being optimized. This failure typically occurs in mixed model objective functions when the marginal variance matrix that describes the mathematical functions of the model parameters is not positive definite, thus resulting in an infeasible solution to the model. In presently known computer-implemented non-linear optimization processes, the model solutions that are iteratively calculated during the optimization process must start at a feasible solution and must remain so during the entire process, otherwise the optimizer will crash or generate an incorrect result. This problem occurs in computer-implemented modeling programs because the computer hardware, more specifically the core processor of the computer, is not capable of handling certain types of calculations due to the limited precision of the computer's processor, or because the computer processor is simply incapable of making certain calculations, such as computing the square root of a negative number.
The objective function of a typical non-linear mixed model may be expressed as follows:
                                             -            likelihood                    =                    ⁢                                                    ∑                j                            ⁢                              log                ⁢                                                                        V                    j                                                                                          +                                          ∑                j                            ⁢                                                r                  j                  T                                ⁢                                  V                  j                                      -                    1                                                  ⁢                                  r                  j                                                      +                          log              ⁢                                                                                    ∑                    j                                    ⁢                                      (                                                                  X                        j                        T                                            ⁢                                              V                        j                                                  -                          1                                                                    ⁢                                              X                        j                                                              )                                                                                                                                    =                    ⁢                                                    ∑                j                            ⁢                              f                1                                      +                                          ∑                j                            ⁢                              f                2                                      +                          f              3                                          where the variable “−likelihood” is the objective function and Vj is the marginal variance matrix. Here, the mixed model objective function is composed of three functions, ƒ1, ƒ2, and ƒ3, and the residual rj is given by the following equation:
                    r        j            =                        Y          j                -                              X            j                    ⁢          β                      ,                  ⁢    with        β    =                            (                                    ∑              j                        ⁢                                          X                j                T                            ⁢                              X                j                                              )                          -          1                    ⁢                        ∑          j                ⁢                              X            j            T                    ⁢                                    Y              j                        .                              The marginal variance matrix Vj is typically dependent on the parameters of the model, and thus a possible parameterization of the mixed model can be given by:V(θ1,θ2)=ZG(θ1)ZT+R(θ2),where Θ1, Θ2 are parameters of the optimization problem, and it is desired to either maximize or minimize the likelihood function (i.e., objective function) with respect to the parameters (Θ1, Θ2).
As noted above, the marginal variance matrix (Vj) must be a positive definite matrix in order for the model to generate a feasible solution. This condition cannot be ignored in such non-linear mixed models, and is typically represented as a non-linear constraint on the optimization problem when maximizing or minimizing the objective function. Unfortunately, in known non-linear optimizers, this implicit non-linear constraint is rarely enforced because it is difficult to implement. Even though the final solution to the problem may have a positive definite matrix Vj, if the initial guess at the solution, as well as any of the iterative guesses made during optimization, yields a non-positive definite matrix for Vj, then the optimizer will typically stop operating or generate an incorrect result.